In wireless local area networks, network devices communicate with each other over a wireless medium that is shared among the network devices. In such cases, in which a wireless medium is shared among multiple network devices, in order to avoid interference among respective transmissions of the network devices on the wireless medium, generally only one networking device should be permitted to transmit on the wireless medium at any given time. When transmissions interfere, such occurrences are commonly referred to as “collisions”. According to IEEE Standard 802.11-2012, the entire disclosure of which is here incorporated by reference, a carrier sense multiple access with collision avoidance (CSMA/CA) scheme is therefore defined.
According to CSMA, prior to transmitting, a network device senses whether the wireless medium is busy—i.e., whether a carrier signal from another station's transmission is present on the wireless medium. If the wireless medium appears to be free based on carrier sensing, a collision avoidance scheme causes the networking device to select a randomized period of time to wait before transmitting. If the wireless medium remains free during this period of time, the network device begins transmitting upon conclusion of the period of time. The networking device expects to receive an acknowledgement from the destination of the transmission. If no acknowledgment is received, the network device may assume that a collision occurred and therefore attempt to retry transmission later, possibly after waiting for an even longer randomized period of time.
In FIG. 1, an example illustration of a collision avoidance scheme consistent with IEEE 802.11 is shown. At time 102, the medium ceases to be busy. A network device that desires to transmit will watch that the medium remains free until time 106, after a delay called the distributed coordination function (DCF) interframe space (DIFS). The network device chooses a random integer between zero and an upper limit, inclusive. This randomized integer may be referred to as a backoff number, a backoff delay, or a backoff interval. The network device then waits for the selected backoff interval and, assuming the medium remains free, begins transmitting.
In FIG. 1, if the randomly selected backoff interval is zero, the network device can begin transmitting at 106. If the backoff interval selected is one, the network device can begin transmitting at 110 after a time period referred to as a slot time. Similarly, if the backoff interval selected is two, the network device can begin transmitting at 114, two slot times after the end of DIFS at 106.
As FIG. 1 demonstrates, DIFS is made up of three time periods, two slot times and one short interframe space (SIFS). Because network devices will normally wait until at least 106 to begin transmitting, even if the selected backoff is zero, an access point can gain precedence over regular network devices by beginning transmission earlier than 106, such as at 118. The delay from time 102 until time 118 is called a point coordination function (PCF) interframe space (PIFS). As seen in FIG. 1, PIFS is formed from SIFS and one slot time.
In FIG. 2, an example transmission following the backoff interval is shown. At 150, a source transmits a request to send (RTS) to a destination. Following a SIFS, during which the destination processes the RTS and gets ready for transmission, the destination transmits a clear to send (CTS) frame at 154. When the source receives a CTS frame, the source knows that the destination successfully received the RTS frame and that a collision did not occur. Because the RTS frame is relatively short, the determination of whether a collision has occurred will be much quicker than if a long data frame experienced a collision. In addition, the CTS frame signals to other network devices, which may not have received the RTS from the source, that a transmission is expected and that the medium is busy.
At 158, after a further SIFS, the source begins transmission of data to the destination. At 162, following another SIFS, the destination transmits an acknowledgment to the source if the destination correctly received the data. At 166, the medium is once again free, and other network devices must wait for at least a period of DIFS until 170 before they can begin transmission. Between 150 and 170, any network devices that had a non-zero backoff would have deferred decrementing their backoff until 170. In other words, if another device had a remaining backoff of two at 150, that backoff would begin decrementing once again at 170. If the medium remains free, after an additional two slot times, the backoff will have decreased to zero and that network device can transmit.
In order to provide quality of service (QoS)—i.e., giving different priorities to different types of traffic—the collision avoidance scheme above, which is called the distributed coordination function (DCF), has been extended with a scheme called enhanced distributed channel access (EDCA). Under EDCA, two primary changes are made. The first is that DIFS is effectively lengthened for lower priority traffic. In addition, the average backoff interval for lower priority traffic is lengthened. The following table includes the four access categories defined for 802.11 QoS. The lowest priority is called background, while the highest priority is called voice.
AccessACCWminCWmaxCategoryDescriptionCWmine.g.CWmaxe.g.AIFSNAC_BKBackgroundaCWmin15aCWmax10237AC_BEBest EffortaCWmin15aCWmax10233AC_VIVideo(aCWmin + 1)/2 − 1 7aCWmin152AC_VOVoice(aCWmin + 1)/4 − 1 3(aCWmin + 1)/2 − 172
When selecting a backoff interval, the network device selects a random number between 0 and an upper limit. The upper limit is called a contention window (CW) and is initialized to a value called CWmin. When a transmission fails, likely as a result of collision, the contention window is increased, up to a limit of CWmax. The above table demonstrates that the values of CWmin and CWmax are different for different access categories.
The CWmin and CWmax values are defined in terms of parameters aCWmin and aCWmax. Using example values of 15 for aCWmin and 1023 for aCWmax, examples of CWmin and CWmax for each access category are shown. For example, for video (AC_VI), the contention window begins at 7 where the backoff will be randomly selected from the range of 0 to 7, and after one or more retries, the backoff will be randomly chosen from the range of 0 to 15.
The above table also has a column for arbitration interframe space number (AIFSN), which specifies the minimum time that the medium must be free before the backoff interval begins. The arbitration interframe space (AIFS) is specified by the sum of SIFS and AISFN times the slot time. As seen in FIG. 3, the AIFS for an AIFSN of two is the same as DIFS from FIG. 1. The AIFS for an AIFSN of three is one slot time longer than DIFS. Similarly, the AIFS for an AIFSN of 7 is five slot times longer than DIFS. In other words, for best effort (AC_BE) frames, where the AIFSN is three, the earliest time a network device could transmit best effort data is at 204. If the selected backoff is one, best effort traffic could be transmitted starting at 208. Similarly, if the backoff is two, best effort traffic could begin transmitting at 212, etc.
Using background data (AC_BK) as an example, the contention window, using the example aCWmin and aCWmax values, increases from 15 to a maximum of 1023 as retransmissions are attempted. Once the contention window reaches CWmax, the contention window remains the same for any subsequent retries. Eventually, after a certain number of retries, transmission of that frame may be abandoned. The function that specifies how the contention window increases from CWmin to CWmax may be dependent on access category. One example function, which is nearly equivalent to doubling, is (CW+1)*2−1. In other words, the contention window begins at 15 and, after an unsuccessful transmission, the CW increases to 31. After another failed transmission attempt, the contention window increases to 63, etc.
Referring again to FIG. 3, it can be observed that the total delay from the medium becoming free until a transmission begins can be expressed in terms of SIFS plus a number of slot times. SIFS is based on the nominal time that the medium access control (MAC) and physical layer interface (PHY) require in order to receive the last symbol of a frame at the air interface, process the frame, and respond with the first symbol on the air interface of the earliest possible response frame. IEEE 802.11-2012, section 6.5.4.2.
The slot time is based on four values: aMACProcessingDelay, aAirPropagationTime, aRxTxTurnaroundTime, and aCCATime. The aMACProcessingDelay value is the maximum time available for the MAC to request a transmission from the PHY after learning of the end of a reception by the PHY. The aAirPropagationTime is twice the propagation time required for a signal to cross the distance between the most distant allowable network devices. The aRxTxTurnaroundTime is the maximum time required by the PHY to change from receiving to transmitting. The aCCATime is the maximum time that a clear channel assessment (CCA) mechanism has available to determine whether the medium is busy or idle. See IEEE 802.11-2012, section 6.5.4.2. For purposes of illustration only, examples of these values in the 5 GHz band are 9 is for slot time, 16 μs for SIFS, and 4 μs for aCCATime.
The background description provided herein is for the purpose of generally presenting the context of the disclosure. Work of the presently named inventors, to the extent the work is described in this background section, as well as aspects of the description that may not otherwise qualify as prior art at the time of filing, are neither expressly nor impliedly admitted as prior art against the present disclosure.